package com.zhugang.week06;

/**
 * @program algorithms
 * @description: binarySearchTree
 * @author: chanzhugang
 * @create: 2022/07/13 15:18
 */
public class BinarySearchTree {

    private Node root;


    /**
     * 查询：非递归实现
     * 时间复杂度: O(logn)
     * 空间复杂度：O(1)
     *
     * @param root
     * @param data
     * @return
     */
    public Node find(Node root, int data) {
        Node p = root;
        while (p != null) {
            if (data < p.data) {
                p = p.left;
            } else if (data > p.data) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    /**
     * 插入
     *
     * @param root
     * @param data
     */
    public void insert(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }
        Node p = root;
        while (p != null) {
            if (data < p.data) {
                // 左子树
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            } else {
                // 右子树
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            }
        }
    }

    /**
     * 删除
     *
     * @param data
     */
    public void delete(int data) {
        // 要删除的节点
        Node p = root;
        // p的父节点
        Node pp = null;
        while (p != null && p.data != data) {
            // 找要删除的节点及其父节点
            pp = p;
            if (data > p.data) {
                p = p.right;
            } else {
                p = p.left;
            }
        }
        if (p == null) {
            // 没有找到
            return;
        }
        // 要删除的节点有两个节点
        if (p.left != null && p.right != null) {
            // 找右子树的最小节点
            Node minP = p.right;
            Node minPP = p;
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;
            p = minP;
            pp = minPP;
        }

        // 删除的节点是叶子节点或者仅有一个子节点
        Node child = null;
        // 找待删除节点p的子节点
        if (p.left != null) {
            child = p.left;
        } else if (p.right != null) {
            child = p.right;
        }

        if (pp == null) {
            // 删除的是根节点
            root = child;
        } else if (pp.left == p) {
            pp.left = child;
        } else {
            pp.right = child;
        }
    }

    public class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {
            this.data = data;
        }
    }
}